1. Field of the Invention
This invention relates to an automatic address management technique for automatically allocating addresses used for discriminating respective hosts connected to a network. More particularly, it relates to an automatic address allocating technique for managing address allocation in a network in which a hierarchical structure is established and which is configured so that an upper order server will allocate an address to a lower order server.
More specifically, the present invention relates to a technique of automatic address allocation and recovery in a system-wide network of a hierarchical structure in which an upper order server allocates an address to a lower order server, wherein address management can be optimally supervised for events such as new connection (addition) or disconnection (deletion) of an external network to the system-wide network, change (migration) of a connecting point of the external network or change of an address in use (re-addressing).
2. Description of Related Art
Nowadays, technical researches into “network computing” of interconnecting computer systems by a network are proceeding briskly. The significance of interconnecting the computers over a network consists in co-owning of computer resources and information circulation and co-owning.
Among communication mediums interconnecting the computers, there are a LAN (Local Area Network) laid in a limited space such as an area within the precincts of enterprises or laboratories and WAN (Wide Area Network) interconnecting the LANs over a dedicated line. Recently, the “Internet”, which is a giant global network, is being used extensively.
The “Internet” is a network having, as a prototype, the APPANET (Advanced Research Projects Agency Network) constructed by the US Department of Defence, and which subsequently is integrated into the NSFNET (National Science Foundation Network) of the US Foundation of Science. In 1995, the backbone part of the network was transferred to a civil organization to mark a starting point of the system-wide network of today. As a result of voluntary interconnection of servers (mainly UNIX workstations) installed in universities or research organizations, the Internet has developed into a global scale network, as the name of the Internet implies. At present, numerous servers are connected to the Internet and are laying open a variety of resource objects to numerous clients.
Meanwhile, addresses termed IP (Internet protocol) addresses have been introduced for uniquely representing hosts on the network distributed world-wide. An IP address is a 32-bit, that is 4-byte address proscribed in a “network layer” termed in an OSI (Open System Interconnection) reference model. The IP address is classified into a “global address” uniquely discriminated on the global scale Internet and a “private address” which is valid only in the private network such as a network laid in a specified enterprise. In the following, discussions are made mainly on the global address.
In the global scale Internet, the world-wide organization, termed IANA (Internet Assigned Numbers Authority), supervises IP global addresses and domain names. The IANA allocates address blocks to low order organizations territorially supervising the IP addresses or domain names, such as InterNIC (Network Information Center) of US, APNIC (Asia Pacific Network Information Center) in Asia-Pacific area or RIPE.NCC (Reseaux IP European network Coordination Centre). These territorial NICs split an allocated address block into a suitable size to allocated the split portion to NICs of respective nations, such as JPNIC. Each Internet service provider (ISP: Internet Service Provider), referred to below simply as a “provider”, acquires an address block from the NIC of each nation belonging to an immediately upper order portion. Also, an enterprise or a university acquires an address block from a provider belonging to an immediately upper order portion to distribute an address block to each business site or laboratory belonging to its lower order portion.
FIG. 12 represents the relation among the servers on the Internet as a hierarchical structure from the standpoint of IP address management or allocation. An upper order server allocates an address block it owns to a lower order server, as described above. Address block allocation usually occurs on request from a lower order server. It should be noted that the relation between an upper order server and a lower order server, shown hierarchically in FIG. 12, does not necessarily mean a physical connection. Stated differently, the hierarchical structure shown in FIG. 12 represents the logical relation formed to meet a network management demand of address block allocation.
The IP address for uniquely discriminating hosts on the Internet is made up of a network address for designating a specified network (LAN) from the external network and a host address for specifying a particular computer connected in the sole network (LAN). The IP address, indispensable for Internet connection, is of a fixed length of 32 bits, such that there is a limit to the number of the IP addresses. Recently, as the number of servers is increasing rapidly, depletion of the IP addresses is thought to be impending.
On the other hand, the physical structure “of the Internet is perpetually changing. That is, the connection or disconnection to or from the network is occurring continually in some portions of the world or a route interconnecting the same points is changing dynamically with e.g., malfunctions of the physical links or routers. Of these changes, those pertinent to address management shown in FIG. 13 are classified into the following four types:                (1) new addition of a network (addition);        (2) removal of a network (deletion);        (3) migration of a network to another place (migration) and        (4) change of network address (re-addressing).        
These can be dealt with by two sorts of operations, namely address “allocation” and address “returing”. For example, in “network addition”, a required address block volume is estimated and allocated. The subject of allocation is determined depending on the scale or properties of the added network, such as Internet service providers (ISP) or a supervisor in an organization.
In “network deletion”, the address so far used needs to be returned. The “network migration” corresponds to change of a provider or connection to another segment in the same provider. In the current Internet, if a provider is changed, it is necessary to request a new address block, and to return an old address, in order not to increase the route information uselessly.
In “re-addressing”, an old address block is recovered and a new address block is allocated in its stead. The “re-addressing” is not necessarily accompanied by changes in the network structure. If, for example, a new address block is necessary due to an increased number of hosts in a network, neighboring address blocks are allocated so as not to increase the route information. If this is not possible, re-addressing is performed. Such re-addressing also becomes necessary in order to adjust the address space which has become sub-divided due to repeated address allocation and retuning.
The Internet is a giant network developed to a global scale, with the structure or the scale of the network or the number of connected computers changing drastically. Notwithstanding, the above-mentioned operations for address allocation are performed by a manual operation. The result is that dynamic changes taking place in every area of the world cannot be coped with, whilst the finite addresses are being used only wastefully, that is, the management efficiency of the Internet is not that high.
Recently, an automatic IP address allocation mechanism, such as “Dynamic Host Configuration Protocol (DHCP)”/*/ or IPv6 Auto Configuration/**/, has been developed.
Of these DHCP is targeted at automating a manual operation required for network construction, and is implemented by installing at least one DHCP server on the network.
In the DHCP server, the necessary information, such as range of the IP network addresses or sub-net mask, is first entered. A client in need of acquiring an IP address first broadcasts a packet (DHCPDISCOVER) for confirming whether or not the DHCP in server is present on the network. On detection of the DHCPDISCOVER packet, the DHCP server broadcasts a responding packet (DHCPOFFER).
The client then is responsive to DHCPOFFER to broadcast an IP address request packet (DHPCREQUEST). The DHCP server determines the IP address and broadcasts the IP address and the sub-net mask (DHCPACK). The client receives the DHCPACK packet to complete acquisition of its own IP address. The DHPC server appends limitations on the lease period of the IP address and allows the client to acquire the IP address again to smooth the re-utilization of the IP address. The IPv6 is a protocol negotiated and standardized by IETF (Internet Engineering Task Force) with a view mainly towards expanding the address space and reducing the routing load.
In IPv6, the Prefix corresponding to the IP network address and the EUI corresponding to the MAC (Media Access Control) address owned inherently by each host are combined together to generate an IPv6 address to realize the function of automatically generating globally unique addresses. By this function, the network user is freed of labor-consuming addressing operations. However, this automatic address setting can be used only in a sole segment, which is a network unit, e.g., a portion from the trailing and to a trailing end of a coaxial cable if the LAN is constructed by this coaxial cable.
These two automatic address allocation mechanisms are targeted at a sole host such that it cannot be applied to network-based automatic address allocation. That is, these automatic address allocation mechanisms lack in scalability.
The present inventors have already proposed a technique termed “Dynamic Network Configuration Protocol (DNCP)”/***/ which has realized the network-based automatic address allocation.
The DNCP first constructs a hierarchical tree structure (spanning tree shown in FIG. 14b), based on a network topology having the physical connection established among respective hosts as shown in FIG. 14a, and performs address allocation in accordance with the tree structure. The scalability can be kept at a higher value by handling the network as a hierarchical model.
FIG. 15 schematically illustrates the address allocation system by DNCP. First, a tree structure among respective servers is formed in accordance with a network topology. In the example shown in FIG. 15, there are two servers S1, S2 as directly lower order servers of a route server RS, whilst there are two servers S3 and S4 as lower order servers with respect to the server S1. Referring to FIG. 15b, the address block initially allocated to the route server RS are suitably split and allocated to the route server RS itself and lower order servers, shown shaded and dotted in FIG. 15b, respectively. The route server RS pools the address block left to itself. Since there is no server as a lower order server to the server S2, that is, there is no server to which to allocate the address, the server S2 also pools the allocated address block. Conversely, since there are servers S3 and S4 as lower order servers to the server S1, the address block needs to be allocated recursively. That is, the address block allocated to the server S1 is suitably split and allocated to the server S1 itself, shown shaded in FIG. 15b, and to the lower order servers S3 and S4, shown dotted in FIG. 15b. The server S1 pools the address block allocated thereto. Similarly, the servers S3 and S4 pool the address block allocated thereto, as shown shaded in FIG. 15b. 
That is, according to DNCP, an upper order server sequentially splits an address block and allocates the split address block to the lower order servers to realize efficient automatic address allocation.
In a network of a smaller scale, its physical structure can be grasped as a static structure. If the structure is dynamic, all changes can be grasped, so that application of DNCP is possible. On the other hand, in the system-wide network, such as Internet, network connection and disconnection occur perpetually somewhere the world, with the physical network structure changing perpetually. The fact that the physical network structure is changing dynamically means that the tree structure for address allocation is also changed. Therefore, the DNCP cannot be directly applied to the global scale network management. That is, the DNCP lacks in scalability.
Annotations
*: As for DHCP, it is disclosed in R. Droms, “Dynamic Host Configuration Protocol” (RFC 2131, March 1997) and in Tominaga, Teraoka and Murai “Problems and Solutions of DHCP” (Proceedings of INET 1995, vol.1, pp.481 to 490, June 1995). The DHCP is defined in RFC (Request for Comments) 1533, 1534, 1541 and 1542. The protocol itself covers application and presentation layers of OSI (Open Systems Interconnection).
**: Pv6 Auto Configuration is described e.g., in A Thomson and T. narten, IPv6 Stateless Address Auto-configuration (RFC 1971 August 1996).
***: DNCP is described e.g., in a treatise by Tominaga, Teraoka and Murai entitled “Dynamic Network Setting Mechanism Employing a Hierarchical Structure” (Computer Software, January 1999, Journal of Japan Society of Software Science, January 1999).